package binary_tree


func IsBst(root *Node) bool {
	if root == nil {return false}
	var vals []int
	fn := func(val int){
		vals = append(vals, val)
	}
	inProcess(root, fn)
	for i:=1; i<len(vals); i++ {
		if vals[i] < vals[i-1] {
			return false
		}
	}
	return true
}

func inProcess(node *Node, fn func(val int)){
	if node == nil {return}
	inProcess(node.Left, fn)
	fn(node.Val)
	inProcess(node.Right, fn)
}

type bstInfo struct {
	isBst bool
	max int
	min int
}

func IsBst2(root *Node) bool {
	if root == nil {return false}
	return BstProcess(root).isBst
}

func BstProcess(node *Node) *bstInfo {
	if node == nil {
		return nil
	}

	leftInfo := BstProcess(node.Left)
	rightInfo := BstProcess(node.Right)
	maxV, minV := node.Val, node.Val
	isBst := false
	if leftInfo != nil {
		minV = min(leftInfo.min, minV)
		maxV = max(leftInfo.max, maxV)
	}
	if rightInfo != nil {
		minV = min(rightInfo.min, minV)
		maxV = max(rightInfo.max, maxV)
	}

	if leftInfo != nil && rightInfo != nil {
		isBst = leftInfo.isBst && rightInfo.isBst && node.Val > leftInfo.max && node.Val < rightInfo.min
	} else if leftInfo != nil && rightInfo == nil {
		isBst = leftInfo.isBst && node.Val > leftInfo.max
	} else if leftInfo == nil && rightInfo != nil{
		isBst = rightInfo.isBst && node.Val < rightInfo.min
	} else {
		isBst = true
	}
	return &bstInfo{isBst, maxV, minV}
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
